class Solution {
public:
    bool isAdditiveNumber(string num) {
        for(int i = 0; i * 2 < num.size(); i++)
            // 注意类型转化！！！！！
            for(int j = 1; i + 1 <= (int)num.size() - i - 1 - j && j <= (int)num.size() - i - 1 - j; j++)
                if (check(num.substr(0, i + 1), num.substr(i + 1, j), num.substr(i + j + 1)))
                    return true;
        return false;
    }
    bool check(string num1, string num2, string rest) {
        if (rest.empty()) return true;
        string sum = add(num1, num2);
        if (num1.size() > 1 && num1[0] == '0' || num2.size() > 1 && num2[0] == '0'||sum.size() > rest.size())
            return false;
        if (sum.size() > rest.size() || sum.size() <= rest.size() && rest.substr(0, sum.size()) != sum) 
            return false;
        bool b = check(num2, sum, rest.substr(sum.size()));
        return b;
    }
    // add 2 number (in string) and output the result in string
    string add(string num1, string num2) {
        int carry = 0;
        string result;
        for(int i = 0; i < max(num1.size(), num2.size()); i++)
        {
            int i1, i2;
            if(i >= num1.size()) i1 = 0;
            else i1 = num1[num1.size() - 1 - i] - '0';
            if(i >= num2.size()) i2 = 0;
            else i2 = num2[num2.size() - 1 - i] - '0';
            int res = i1 + i2 + carry;
            if (res > 9)
            {
                carry = 1;
                result.insert(0, 1, '0' + (char)(res - 10));
            }
            else
            {
                carry = 0;
                result.insert(0, 1, '0' + (char)(res));
            }
        }
        if (carry)
            result.insert(0, 1, '1');
        return result;
    }
};
